/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：KdTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-05-11
Function List ：
Description   ：2d-Tree
******************************************************/

#include "KdTree.h"
#include <stdio.h>   // for printf
#include <stdlib.h>  // for malloc
#include "FatalError.h"

struct KdNode {
    ItemType Data;
    KdTree   Left;
    KdTree   Right;
};

// Static Function Lists
__attribute__((unused)) static KdTree RecursiveInsert(ItemType Item, KdTree T, int Level);
__attribute__((unused)) static KdTree NonrecursiveInsert(ItemType Item, KdTree T, int Level);
static void RecPrintRange(ItemType Low, ItemType High, KdTree T, int Level);

KdTree Initialize(void) {
    return NULL;
}

KdTree Destroy(KdTree T) {
    if (T != NULL) {
        Destroy(T->Left);
        Destroy(T->Right);
        free(T);
    }

    return NULL;
}

int IsEmpty(KdTree T) {
    return T == NULL;    
}

static KdTree RecursiveInsert(ItemType Item, KdTree T, int Level) {
    if (T == NULL) {
        T = (KdTree)malloc(sizeof(struct KdNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        }

        T->Left = NULL;
        T->Right = NULL;
        T->Data[0] = Item[0];
        T->Data[1] = Item[1];
    } else if (Item[Level] < T->Data[Level]) {
        T->Left = RecursiveInsert(Item, T->Left, !Level);
    } else {
        T->Right = RecursiveInsert(Item, T->Right, !Level);
    }

    return T;
}

static KdTree NonrecursiveInsert(ItemType Item, KdTree T, int Level) {
    Position NewCell;
    Position Tmp;
    Position Pre;

    Tmp = T;
    while (Tmp != NULL) {
        Pre = Tmp;
        if (Item[Level] < Tmp->Data[Level]) {
            Tmp = Tmp->Left;
        } else if (Item[Level] >= Tmp->Data[Level]) {
            Tmp = Tmp->Right;
        }

        Level = !Level;
    }

    /* New Node */
    NewCell = (KdTree)malloc(sizeof(struct KdNode));
    if (NewCell == NULL) {
        FatalError("Out of space!!!");
    }

    NewCell->Left = NULL;
    NewCell->Right = NULL;
    NewCell->Data[0] = Item[0];
    NewCell->Data[1] = Item[1];

    /* Insert the first nodes */
    if (T == NULL) {
        T = NewCell;
    } else {
        Level = !Level;
        if (Item[Level] < Pre->Data[Level]) {
            Pre->Left = NewCell;
        } else if (Item[Level] >= Pre->Data[Level]) {
            Pre->Right = NewCell;
        }
    }

    return T;
}

KdTree Insert(ItemType Item, KdTree T) {
    // return RecursiveInsert(Item, T, 0);
    return NonrecursiveInsert(Item, T, 0);
}

/* Print items satisfying */
/* Low[0] <= Item[0] <= High[0] and */
/* Low[1] <= Item[1] <= High[1] */
static void RecPrintRange(ItemType Low, ItemType High, KdTree T, int Level) {
    if (T != NULL) {
        if (Low[0] <= T->Data[0] && T->Data[0] <= High[0] &&
            Low[1] <= T->Data[1] && T->Data[1] <= High[1]) { 
            printf("(%d, %d)\n", T->Data[0], T->Data[1]);
        }

        if (Low[Level] <= T->Data[Level]) {
            RecPrintRange(Low, High, T->Left, !Level);
        }

        if (High[Level] >= T->Data[Level]) {
            RecPrintRange(Low, High, T->Right, !Level);
        }
    }
}

void PrintRange(ItemType Low, ItemType High, KdTree T) {
    RecPrintRange(Low, High, T, 0);
}

// EOF

